// ANSWER: 5943040885644

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>
#include "prime.h"

// LOWER_BOUND_MODE controls how we estimate the lower bound of n during recursion.
//  0 - do not use lower bound
//  1 - compute lower bound in each routine
//  2 - pass lower bound as a parameter (NOT IMPLEMENTED)
#define LOWER_BOUND_MODE 1

// Let the `power representation' of a positive integer 
//   n = p1^k1 * p2^k2 * ... * pm^km
// be the vector (k1, k2, ..., km).
typedef std::vector<int> power_representation;

static long long call_counter = 0;

// Return the minimum number p^m such that p^(m+k) is a cube.
static long long cube_mult(int p, int k)
{
	assert(k >= 0);
	k %= 3;
	return (k==1)? (long long)p*p : (k==2)? p : 1;
}

#if 1
// Let phi(n^2) = p1^l1 * ... * pm^lm
// When we call the function, for every j > i, l_j is guaranteed to be 
// a multiple of 3.
static long long search(
	long long N, long long n, long long lb_mult,
	const std::vector<int> &primes, int i, 
	const std::vector<std::pair<int,int>> &factors, const std::vector<int> &factor_pos,
	power_representation &L)
{
	call_counter++;
	assert(i >= 0);

	// If L[m] is already a multiple of 3, then we can optionally skip this 
	// prime factor in the construction of n.
	long long ret = 0;
	if (L[i] % 3 == 0)
	{
		ret += (i==0)? n : search(N, n, lb_mult, primes, i-1, factors, factor_pos, L);
	}
#if LOWER_BOUND_MODE==2
	lb_mult /= cube_mult(primes[i], L[i]);
#endif

	// Now we try k_i >= 1. Update L(i) for 1 <= i <= m-1.
	for (int j = factor_pos[i]; j < factor_pos[i+1]; j++)
	{
#if LOWER_BOUND_MODE==2
		lb_mult /= cube_mult(primes[factors[j].first], L[factors[j].first]);
#endif
		L[factors[j].first] += factors[j].second;
	}
#if LOWER_BOUND_MODE==2
	for (int j = factor_pos[i+1] - 1; j >= factor_pos[i]; j--)
	{
		lb_mult *= cube_mult(primes[factors[j].first], L[factors[j].first]);
		if (lb_mult * n > N)
			break;
	}
#endif

	// Estimate a lower bound of n. If the lower bound is greater than N, then
	// we needn't recurse further any more.
#if LOWER_BOUND_MODE==1
	lb_mult = 1;
	for (int j = i - 1; j >= 0; j--)
	{
		if (L[j] > 0)
		{
			lb_mult *= cube_mult(primes[j], L[j]);
			break;
		}
	}
#endif

	int p = primes[i];
	int old_L_i = L[i];
	for (int k = 1; (n *= p) <= N / lb_mult; k++)
	{
		if ((old_L_i + 2*k-1) % 3 == 0)
		{
			L[i] = old_L_i + 2*k-1;
			ret += (i==0)? n : search(N, n, lb_mult, primes, i-1, factors, factor_pos, L);
		}
	}

	// Restore phi to continue recursion.
	L[i] = old_L_i;
	for (int j = factor_pos[i]; j < factor_pos[i+1]; j++)
	{
		L[factors[j].first] -= factors[j].second;
	}
	return ret;
}
#else
// Let phi(n^2) = p1^l1 * ... * pm^lm
// When we call the function, for every j > i, l_j is guaranteed to be 
// a multiple of 3.
static long long search(
	long long N, long long n, 
	const std::vector<int> &primes, int i, 
	const std::vector<std::pair<int,int>> &factors, const std::vector<int> &factor_pos,
	power_representation &phi)
{
	// Recursion tail
	if (i < 0)
	{
		// std::cout << "n = " << n << std::endl;
		return n;
	}

	// If k_i is already a multiple of 3, then we can optionally skip this 
	// prime factor in the construction of n.
	long long ret = 0;
	if (phi[i] % 3 == 0)
	{
		ret += search(N, n, primes, i-1, factors, factor_pos, phi);
	}

	// Now we add factors into n. Once we add this, we need to add (p-1) to phi.
	for (int j = factor_pos[i]; j < factor_pos[i+1]; j++)
	{
		phi[factors[j].first] += factors[j].second;
	}

	int p = primes[i];
	int old_phi_i = phi[i];
	for (int k = 1; (n *= p) <= N; k++)
	{
		if ((old_phi_i + 2*k-1) % 3 == 0)
		{
			phi[i] = old_phi_i + 2*k-1;
			ret += search(N, n, primes, i-1, factors, factor_pos, phi);
		}
	}

	// Restore phi to continue recursion.
	phi[i] = old_phi_i;
	for (int j = factor_pos[i]; j < factor_pos[i+1]; j++)
	{
		phi[factors[j].first] -= factors[j].second;
	}
	return ret;
}
#endif

static int verify(int N)
{
	int sum = 0;
	for (int n = 2; n < N; n++)
	{
		int t = totient(n*n);
		int x = (int)pow((double)t, 1.0/3.0);
		if (x*x*x == t || (x+1)*(x+1)*(x+1) == t)
		{
			// std::cout << "n = " << n << std::endl;
			sum += n;
		}
	}
	return sum;
}

void solve_problem_342()
{
#if 0
	//const long long N = 100 - 1;
	const long long N = 10000LL - 1;
#else
	const long long N = 10000000000LL - 1;
#endif

	// std::cout << "verify = " << verify(N) << std::endl;

	// Find all prime factors below sqrt(N).
	int sqrt_n = (int)sqrt((double)N);
	std::vector<int> primes;
	find_primes_below(sqrt_n+1, primes);

	// For each prime factor p, do a prime-factorization of (p-1).
	// The list of all factors (p-1) are stored consecutively in _factors_.
	// The start position of the i-th factorization is stored in _factor_pos_.
	std::vector<std::pair<int,int>> factors;
	std::vector<int> factor_pos(primes.size()+1);
	for (int i = 1; i < (int)primes.size(); i++)
	{
		int t = primes[i] - 1;
		for (int j = 0; ; j++)
		{
			int pp = primes[j];
			if (pp*pp > t)
				break;
			int kk = 0;
			while (t % pp == 0)
			{
				t /= primes[j];
				kk++;
			}
			if (kk > 0)
				factors.push_back(std::pair<int,int>(j, kk));
		}
		if (t > 1)
		{
			int j = (int)(std::lower_bound(primes.cbegin(), primes.cend(), t) - primes.cbegin());
			factors.push_back(std::pair<int,int>(j, 1));
		}
		factor_pos[i+1] = (int)factors.size();
	}

	// Start with the last prime. Search through all possible combinations.
	power_representation phi(primes.size());
	long long sum = search(N, 1, 1, primes, (int)primes.size()-1, factors, factor_pos, phi); 
	std::cout << (sum - 1) << std::endl;
	// std::cout << "Calls: " << call_counter << std::endl;
}
